/**
 * @author 03010570
 * @date 2020/07/15
 * describe:    LeetCode : 96、不同的二叉搜索树  https://leetcode-cn.com/problems/unique-binary-search-trees/
 */
public class LeetCode_96 {
    public static void main(String[] args) {
        System.out.println(numTrees(1));
        System.out.println(numTrees(2));
        System.out.println(numTrees(3));
        System.out.println(numTrees(4));
    }

    /**
     * 当前节点 ：dp[i] = dp[i-1] * dp[n-i]
     * 左子树的个数 ： i-1
     * 右字数的个数 ： n-i
     *  时间复杂度 ： O(N^2)
     *  空间辅助度 ： O(N)
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j < i + 1; j++) {
                res[i] += res[j - 1] * res[i - j];
            }
        }
        return res[n];

    }
}
